package com.mori.algorithm;

import java.util.Arrays;

/**
 * <p> 排序  </p>
 *
 * @author mori
 * @since 10/22/2019 4:59 PM
 */
public class Sort {

    public static void main(String[] args) {
        int[] arr = {1, 6, 3, 4, 9, 5, 0};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int low, int high) {
        // 结束标志
        if (low >= high) {
            return;
        }
        // 低位下标
        int first = low;
        // 高位下标
        int last = high;
        // 设第一个为基准
        int key = arr[first];

        while (first < last) {
            // 将比第一个小的移到前面
            while (first < last && arr[last] >= key) {
                --last;
            }
            if (first < last) {
                // 这里是替换而不是交换
                arr[first++] = arr[last];
            }

            // 将比第一个大的移到后面
            while (first < last && arr[first] <= key) {
                ++first;
            }
            if (first < last) {
                // 这里是替换而不是交换
                arr[last--] = arr[first];
            }
        }
        // 基准置位
        // 但是到这里的时候，数组里的元素只是换了位置，而没有丢失掉任何一个
        arr[first] = key;
        // 前半递归
        quickSort(arr, low, first - 1);
        // 后半递归
        quickSort(arr, first + 1, high);
    }
}
